/* 
 * Code for basic C skills diagnostic.
 * Developed for courses 15-213/18-213/15-513 by R. E. Bryant, 2017
 * Modified to store strings, 2018
 */

/*
 * This program implements a queue supporting both FIFO and LIFO
 * operations.
 *
 * It uses a singly-linked list to represent the set of queue elements
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#include "harness.h"
#include "queue.h"

/*
  Create empty queue.
  Return NULL if could not allocate space.
*/
queue_t *q_new()
{
    queue_t *q =  malloc(sizeof(queue_t));
    /* What if malloc returned NULL? */

    /* MY CODING */
    if (q == NULL) return NULL;
    q->tail = NULL;
    q->head = NULL;
    q->size = 0;
    /* MY CODING */

    return q;
    
}

/* Free all storage used by queue */
void q_free(queue_t *q)
{
    if (q == NULL) return;
    /* How about freeing the list elements and the strings? */

    /* MY CODING */
    list_ele_t* t = q->head;
    while (t != NULL) {
        list_ele_t* temp = t;
        free(temp->value); // free string
        t = t->next;
        free(temp); // free list element
    }
    /* MY CODING */

    /* Free queue structure */
    free(q);
}

/*
  Attempt to insert element at head of queue.
  Return true if successful.
  Return false if q is NULL or could not allocate space.
  Argument s points to the string to be stored.
  The function must explicitly allocate space and copy the string into it.
 */
bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    /* What should you do if the q is NULL? */

    /* MY CODING */
    if (q == NULL) return false;
    newh = malloc(sizeof(list_ele_t));

    if (newh == NULL) return false;

    /* Don't forget to allocate space for the string and copy it */
    newh->value = (char*)malloc(strlen(s) + 1); 
    /* What if either call to malloc returns NULL? */
    if (newh->value == NULL) { 
        free(newh); // 第二次分配不成功记得把第一次分配的也free掉
        return false;
    } 
    newh->value = strncpy(newh->value, s, strlen(s)+1);

    newh->next = q->head;
    q->head = newh;
    q->size++;
    if (q->tail == NULL) q->tail = newh;
    /* MY CODING */

    return true;
}


/*
  Attempt to insert element at tail of queue.
  Return true if successful.
  Return false if q is NULL or could not allocate space.
  Argument s points to the string to be stored.
  The function must explicitly allocate space and copy the string into it.
 */
bool q_insert_tail(queue_t *q, char *s)
{
    /* You need to write the complete code for this function */
    /* Remember: It should operate in O(1) time */

    list_ele_t *newh;
    /* What should you do if the q is NULL? */

    /* MY CODING */
    if (q == NULL) return false;
    newh = malloc(sizeof(list_ele_t));

    if (newh == NULL) return false;

    /* Don't forget to allocate space for the string and copy it */
    newh->value = (char*)malloc(strlen(s) + 1); 
    /* What if either call to malloc returns NULL? */
    if (newh->value == NULL) {
        free(newh);
        return false;
    }
    newh->value = strncpy(newh->value, s, strlen(s)+1);

    newh->next = NULL;
    if (q->size == 0) q->head = q->tail = newh;
    else {
        q->tail->next = newh;
        q->tail = newh;
    }

    q->size++;
    /* MY CODING */

    return true;
}

/*
  Attempt to remove element from head of queue.
  Return true if successful.
  Return false if queue is NULL or empty.
  If sp is non-NULL and an element is removed, copy the removed string to *sp
  (up to a maximum of bufsize-1 characters, plus a null terminator.)
  The space used by the list element and the string should be freed.
*/
bool q_remove_head(queue_t *q, char *sp, size_t bufsize)
{
    /* You need to fix up this code. */
    
    /* MY CODING */
    if (q == NULL || q->head == NULL ) return false;

    int i = 0;

    if (sp != NULL) { 
        while (i < bufsize-1 && q->head->value[i] != '\0') {
            sp[i] = q->head->value[i];
            i++;
        }
        sp[i] = '\0';
    }

    list_ele_t *tmp = q->head;
    q->head = q->head->next;

    free(tmp->value);
    free(tmp);
    --q->size;
    /* MY CODING */

    return true;
}

/*
  Return number of elements in queue.
  Return 0 if q is NULL or empty
 */
int q_size(queue_t *q)
{
    /* MY CODING */
    if (q == NULL || q->head == NULL) return 0;
    /* You need to write the code for this function */
    /* Remember: It should operate in O(1) time */
    return q->size;
    /* MY CODING */
}

/*
  Reverse elements in queue
  No effect if q is NULL or empty
  This function should not allocate or free any list elements
  (e.g., by calling q_insert_head, q_insert_tail, or q_remove_head).
  It should rearrange the existing ones.
 */
void q_reverse(queue_t *q)
{
    /* MY CODING */
    if ( q == NULL || q->head == NULL || q->head->next == NULL ) return;

    list_ele_t *old_head = q->head;
    list_ele_t *old_tail = q->tail;

    list_ele_t *tmp = q->head->next;
    q->head->next = NULL;

    while (tmp != NULL) {
        list_ele_t *tmp_next = tmp->next;
        tmp->next = q->head;
        q->head = tmp;
        tmp = tmp_next;
    }

    // 重新设置表头表尾
    q->head = old_tail;
    q->tail = old_head;
    /* MY CODING */

    /* You need to write the code for this function */
}

